NOI.1.13.11 回文素数（C++

您所在的位置：网站首页 › openjudge 13 › NOI.1.13.11 回文素数（C++

NOI.1.13.11 回文素数（C++

2023-03-24 03:46| 来源: 网络整理| 查看: 265

NOI.1.13.11 回文素数

NOI.1.13.11 回文素数（C++）

全局题号2248，题目原址：http://noi.openjudge.cn/ch0113/11/ 题为输入n，统计并输出所有回文素数的n位数，根据实际情况修改以满足题意这道题可以取到9位数，导致我一开始用筛选质数表记录，结果空间limited，改为用较高效的素数判断法也超时。看了一大哥帖子思路后瞬间点醒（那帖子找不到链接了道歉）（找到了在后面）。同时判断回文和素数，老老实实枚举下去容易超时，要缩小解集快速进行某一步（要么耍流氓直接用已用质数表，要么生成出n位的回文数不再判断回文）。素数判断用到了数论的知识略过了很多解空间，同样回文素数后来debug发现了n大于2的偶数位下存在的规律。代码如下，一些解释看后头

#include #include using namespace std; bool isPrime(int n){ //素数存在定理，大于3的素数必处于6的倍数两端 if(n1; if(n%6!=1&&n%6!=5)return false; //不为6倍数附近则不是素数 for(int i = 5 ; i*i2&&N%2==0)return ; //跳过所有大于2的偶数次位，必为11的倍数，数量为0 int f,k; f = N%2==1?10:1; //f 控制奇偶情况的不同处理方式 k = N/2; //k指明乘几次10，以给后续留出位置 for(int i = x ;iN; n = (N+1)/2; // n为N的折半位数 int X = 1, Y = 0; //X，Y经处理后变为半N位数下的取数范围 [ X, Y ] while(n>0){ X = 10*X; Y = 10*Y+9; n--; } X/=10; vector Res, tab; generatePal(tab,X,Y,N); //生成N位的回文数组 for(int i = 0;i

【本文地址】

NOI.1.13.11 回文素数（C++

NOI.1.13.11 回文素数（C++

今日新闻

推荐新闻

NOI.1.13.11 回文素数 （C++

NOI.1.13.11 回文素数 （C++

今日新闻

推荐新闻

NOI.1.13.11 回文素数（C++

NOI.1.13.11 回文素数（C++